package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

//深度优先遍历，因为先遍历到最左边
func levelOrder(root *TreeNode) [][]int {
	res := [][]int{}

	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, depth int) {
		if node == nil {
			return
		}
		if len(res) <= depth {
			res = append(res, []int{})
		}
		res[depth] = append(res[depth], node.Val)
		dfs(node.Left, depth+1)
		dfs(node.Right, depth+1)
	}

	dfs(root, 0)
	return res
}

func main() {
	var a, b TreeNode
	b.Val = 10
	a.Left = &b
	fmt.Println(a, b)
	fmt.Println(levelOrder(&a))
	fmt.Println(levelOrder1(&a))
	res := [][]int{}
	fmt.Println(len(res), res)
	res = append(res, []int{0, 1})
	fmt.Println(len(res), res, res[0])
	nodes := []*TreeNode{&a}
	fmt.Println(nodes, len(nodes))

}

//再研究
func levelOrder1(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}

	res := [][]int{}
	nodes := []*TreeNode{root}
	for len(nodes) > 0 {
		nodesLen := len(nodes)
		values := []int{}
		for i := 0; i < nodesLen; i++ {
			values = append(values, nodes[i].Val)
			if nodes[i].Left != nil {
				nodes = append(nodes, nodes[i].Left)
			}
			if nodes[i].Right != nil {
				nodes = append(nodes, nodes[i].Right)
			}
		}
		res = append(res, values)
		nodes = nodes[nodesLen:] // 切掉本层的结点，留下***结点
	}

	return res
}
